Content addressable memory (CAM) devices, sometimes also referred to as “associative memories”, can provide rapid matching functions between an applied data value (e.g., a search key, comparand, or compare data value) and stored data values (e.g., entries). Such rapid matching functions are often utilized in routers, network switches, and the like, to process network packets.
Most CAM devices have an inherent “hard” priority between entries, usually established according to physical location (e.g., address). In addition, some CAM devices have included “soft” priority values that allow sections of a CAM device to be programmed to have a particular priority with respect to other sections of the same CAM device.
A conventional CAM device having soft priority capabilities is shown in a block schematic diagram in FIG. 9. A CAM device can have a number of “super-blocks” (shown as SB0 to SB3), each of which can include a number of “m” sub-blocks. Each super-block can include a corresponding result prioritizer RP0 to RP3. Each result prioritizer can receive a sub-block result and soft-priority value for each sub-block of the corresponding super-block. In one particular example, a sub-block result can include an address value of nineteen bits while a soft-priority value can be an eight-bit value. A result prioritizer can determine a highest priority result from the sub-blocks of the corresponding super-block.
Referring to FIG. 9, in operation, a winning (i.e., highest priority) match result from the sub-blocks within super-block SB3 (and any upstream super-blocks) can be forwarded to result prioritizer RP2 as a super-block SB3 result. Result prioritizer RP2 can determine a highest priority result from among its own sub-block results as well as the received super-block result from RP3, and output its own super-block result to the next super-block downstream (in this case super-block SB1).
In this way, super-block results are prioritized in a cascaded fashion to generate a prioritized super-block group result.
FIG. 10 shows a result prioritizer 1000 like those shown as RP0 to RP3 in FIG. 9. Result prioritizer 1000 can receive match results and local priority values from sub-blocks of a super-block. FIG. 10 shows an example in which match results and soft priority values are received for four sub-blocks. First comparators 1002-0 and 1002-1 can compare soft priority and match result value to control corresponding multiplexers (MUXs) 1004-0 to 1004-3 to output a higher priority match result and soft priority values. These values can be further prioritized by comparator 1002-2, which can control MUXs 1006-0 and 1006-1, which can output a highest priority match result and soft priority value, respectively, from among all sub-blocks.
Comparator 1008 can compare a highest priority match result from the sub-blocks of the corresponding super-block with those of a received “upstream” super-block. Comparator 1008 can control MUXs 1010-0 and 1010-1, which can output a highest priority match result and soft priority value, respectively, from among all sub-blocks.
It is understood that the comparators described above compare sub-block match results and soft-priority values with one another, and so can be relatively large circuits. Thus, if a match result was a nineteen-bit value and a soft-priority value was and eight bit value, such comparators would compare at least 27 bits with one another.
A drawback to a conventional approach, like that of FIG. 10 can be the propagation time involved in having results propagate through multiple result prioritizers (e.g. RP0 to RP3). This introduces considerable delay into a time critical path (match result path) of a CAM device.
A second conventional CAM device having soft priority capabilities is shown in a block schematic diagram in FIG. 11. A CAM device can have a number of “super-blocks” (shown as SB0 to SB5), each of which can include a number of “m” sub-blocks (in the example shown, m=4). Each super-block can include a corresponding result prioritizer (RP0 to RP5). In one arrangement, each super-block includes a 1 to 4 de-multiplexer. Sub-block match results and soft priority values can be driven between super-blocks on a super-block bus, which can include m buses.
In the conventional approach of FIG. 11, each super-block can drive sub-block results (with corresponding soft priority values) onto corresponding result buses.
A drawback to the approach of FIG. 11 can be the size of result buses. For example, in one arrangement, each result bus can include 28 bus lines: 19 address lines, one hit indication line, and 8 soft-priority lines. This results in a total of 112 bus lines. All of the above can require large substrate and/or routing areas.